\vspace{-5pt}
\section{SLP Algorithm}
\label{sec:algorithm}
\vspace{-5pt}
The basic idea of SLP algorithm is to identify \textbf{isomorphic} statements,
which are statements that contain the same operations in the same order. If we can find
independent isomorphic statements, we could package them into a SIMD
instruction, and get them executed in parallel. 

The algorithm first looks up adjacent memory operations (Load and Store), and
combines them into a \textit{Pack}. For example \texttt{Load a[0]} and
\texttt{Load a[1]} are adjacent because the target addresses are consecutive. Then
the algorithm tries to expand the Packs in two dimensions, wider Pack and more
Packs. First it checks if there are two packs such as,\{\textit{s1},
\textit{s2}\}, and \{\textit{s2}, \textit{s3}\}, that can be merged into \{\textit{s1},
\textit{s2}, \textit{s3}\}. The second pass follows the use-def chain and def-use
chains to find new candidates that can either produce needed source operands in
packed form, or use existing packed data as source operands. If these candidates
are isomorphic statements, new Packs are identified.

After identifying packs, the algorithm then schedules these statements in the basic
block, and make sure all statements in one Pack are scheduled together. It may
break some Packs into individual statements because of data dependence or memory
dependence violation. If the Pack can be scheduled successfully, it will be
replaced by one SIMD instruction.If this new operation requires operand packing
or requires unpacking the result, the required instructions are inserted.

The SLP algorithm includes seven steps, which is described in section 3 of
\cite{SLP}. We slightly changed some steps of the algorithm, and here are the
details.

\textbf{Alignment analysis} We didn't implement this part in our algorithm, and
we simply rely on LLVM to align each memory access after vectorization.

\textbf{Identifying Adjacent Memory References} In LLVM all direct memory
access are based on GetElementPtrInst statements. Our analysis just detects whether two
pointers returned by two GetElementPtrInst are adjacent. Then we follow the def-use
chain and the use-def chain to identify all ajacent load and store statements. But
if the memory operation uses indirect memory address, e.g. a[b[i]], we cannot
prove whether two b[i] are adjacent, and there is no Pack identified.

\textbf{Scheduling} The original algorithm described in the SLP paper merges the
instruction scheduling and emitting code in the same algorithm. Each
time a Pack is scheduled, it will replace it with a new SIMD, and insert
packing and unpacking statements as required. In the implementation process, we
found mixing scheduling and emitting together makes the code very complex, we
divide this step into two. The new scheduling only re-orders the original
statements in a valid way, and make sure each statements in a Pack is placed
consecutively. The code replacement is in the Emitting Code step.

\textbf{Emitting Code} The SLP paper didn't give the algorithm of how to do code
replacement and insert pack and unpack code. Here is the algorithm we used.
Please note this algorithm targets LLVM IR.

\lstset{language=C}
\begin{lstlisting}
emit_code(BasicBlock B, PackSet P) 
{
  for (s in B ) {
    if(! is_belong_to_pack(s, P) {
      continue; //move to next statement
    }
    s is the first statement in a Pack [s1, s2, ... ]
    if( s is a GetElementPtrInst) {
      ignore all GetElementPtrInst statements in the pack; 
      continue;
    }
    sVec = gen a vector version of s1
    for( i in num of operands of s1 ) {
      if( s is a memory operation && s.op(i) is a GetElementPtrInst) {
         sVec.op(i) = s1.op(i); //just use the first statement's pointer
      } else {
        sVec.op(i) = gen packing statements from [s1.op(i), s2.op(i), ...]
      }
    }
    if( s has return value ) {
       [sVec_unpack1, sVec_unpack2, ...] = gen unpacking statements of sVec
       replace all use of [s1, s2, ... ] with the [sVec_unpack1,sVec_unpack2, ...] 
    }
    insert sVec and all packing/unpacking statements.
    remove [s1, s2, ... ]
    move to the statement after the pack
}
\end{lstlisting}

We ignore processing GetElementPtrInst in the algorithm because if the Pack
contains GetElementPtrInst with adjacent memory reference, the first
GetElementPtrInst statement will be used in the vector version of memory
operation statement. If the Pack contains GetElementPtrInst with non-adjacent
memory reference, there is no SIMD to present this operation, and we still need to
maintain the original format. The reason that one Pack may contain
GetElementPtrInst with non-adjacent memory reference is that the extending pack
algorithm follows use-def chain, and may pack the GetElementPtrInst statements
together. 
